/**
 *  参考:
 *      https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
 *
 *  在此规定:
 *      前序遍历的顺序: 根->左->右
 *      中序遍历的顺序: 左->根->右
 *      后序遍历的顺序: 左->右->根
 *      层序遍历的顺序: 每一层从左->右
 */

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <functional>

using namespace std;

/// @brief 二叉树的节点
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right)
        : val(x), left(left), right(right)
    {
    }
};

/// @brief 前序遍历 迭代版
/// @note 注意先压栈右节点, 再压栈左节点, 这样才能让访问
///       顺序是: 根->左->右
vector<int> preorder(TreeNode *root)
{
    vector<int> ret;
    if (!root)
        return ret;

    stack<TreeNode *> st;
    st.push(root);
    while (st.size()) {
        // 先访问当前节点
        TreeNode *cur = st.top();
        st.pop();
        ret.push_back(cur->val);

        // [先] 右节点压栈
        if (cur->right) {
            st.push(cur->right);
        }
        // 左节点压栈
        if (cur->left) {
            st.push(cur->left);
        }
    }
    return ret;
}

/// @brief 中序遍历 迭代版
///     每次先将左子树压栈(走到最左边),
///     然后出栈访问栈顶节点, 然后右子树准备压栈.
vector<int> inorder(TreeNode *root)
{
    vector<int> ret;
    stack<TreeNode *> st;
    TreeNode *cur = root;

    while (cur || st.size()) {
        // 不断压栈左节点, 直到最左边
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }

        // 访问当前节点
        cur = st.top();
        st.pop();
        ret.push_back(cur->val);

        // 右子树准备到下一轮循环 进行压栈
        cur = cur->right;
    }

    return ret;
}

/// @brief 后序遍历 迭代版
///     用两个栈更舒服一些.
vector<int> postorder(TreeNode *root)
{
    vector<int> ret;
    if (!root)
        return ret;

    stack<TreeNode *> st1, st2;
    st1.push(root);
    while (st1.size()) {
        // 根节点压栈到st2中
        TreeNode *node = st1.top();
        st1.pop();
        st2.push(node);

        // 左节点压栈到st1中
        if (node->left)
            st1.push(node->left);

        // 右节点压栈到st1中
        if (node->right)
            st1.push(node->right);
    }
    // 在这之后, st2 里的顺序自底向上就是 根->右->左
    // 按顺序出栈 st2 就能得到 左->右->根

    while (st2.size()) {
        TreeNode *node = st2.top();
        st2.pop();
        ret.push_back(node->val);
    }
    return ret;
}

///////////////////// 前中后序递归版本 无需多言 /////////////////////
/// @brief 前序遍历 递归版
vector<int> preorder_dfs(TreeNode *root)
{
    vector<int> ret;
    function<void(TreeNode *)> dfs = [&](TreeNode *root) {
        if (!root)
            return;
        ret.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    };

    dfs(root);
    return ret;
}

/// @brief 中序遍历 递归版
vector<int> inorder_dfs(TreeNode *root)
{
    vector<int> ret;
    function<void(TreeNode *)> dfs = [&](TreeNode *root) {
        if (!root)
            return;
        dfs(root->left);
        ret.push_back(root->val);
        dfs(root->right);
    };

    dfs(root);
    return ret;
}

/// @brief 后序遍历 递归版
vector<int> postorder_dfs(TreeNode *root)
{
    vector<int> ret;
    function<void(TreeNode *)> dfs = [&](TreeNode *root) {
        if (!root)
            return;
        dfs(root->left);
        dfs(root->right);
        ret.push_back(root->val);
    };

    dfs(root);
    return ret;
}
///////////////////// 前中后序递归版本 无需多言 /////////////////////

/// @brief 层序遍历 迭代版
///        直接用队列, 无需多言
vector<vector<int> > levelorder(TreeNode *root)
{
    vector<vector<int> > ret;
    if (!root)
        return ret;
    queue<TreeNode *> q;
    q.push(root);
    while (q.size()) {
        int cur_size = q.size();
        vector<int> v;
        while (cur_size--) {
            TreeNode *node = q.front();
            q.pop();
            v.push_back(node->val);
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
        ret.push_back(v);
    }
    return ret;
}

/// @brief 层序遍历 递归版
///     记录 vector<vector<int>> ret 数组的下标, 作为二叉树的层级
///     例如 ret[2] 就表示二叉树的第二层的所有节点.
vector<vector<int> > levelorder_dfs(TreeNode *root)
{
    vector<vector<int> > ret;
    function<void(TreeNode *, int)> dfs = [&](TreeNode *root, int level) {
        if (!root)
            return;

        // 第一次进入当前层级,
        // 为 ret 增加一个空数组
        if (ret.size() == level)
            ret.emplace_back(vector<int>());

        // 添加当前层的一个节点
        ret[level].emplace_back(root->val);

        // 注意递归的时候先左后右,
        // 否则每一层的顺序会乱
        dfs(root->left, level + 1);
        dfs(root->right, level + 1);
    };
    dfs(root, 0);
    return ret;
}

void testTraversal(const string &name, const vector<int> &result)
{
    cout << name << ": ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
}

void testLevelOrder(const string &name, const vector<vector<int> > &result)
{
    cout << name << ": ";
    for (const auto &level : result) {
        for (int val : level) {
            cout << val << " ";
        }
    }
    cout << endl;
}

int main()
{
    // 构建一棵二叉树
    //        1
    //       / \
    //      2   3
    //     / \ / \
    //    4  5 6  7
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    // 测试前序遍历
    testTraversal("Preorder Iterative", preorder(root));
    testTraversal("Preorder Iterative", preorder_dfs(root));

    // 测试中序遍历
    testTraversal("Inorder Iterative", inorder(root));
    testTraversal("Inorder Iterative", inorder_dfs(root));

    // 测试后序遍历
    testTraversal("Postorder Iterative", postorder(root));
    testTraversal("Postorder Iterative", postorder_dfs(root));

    // 测试层序遍历
    testLevelOrder("Levelorder Iterative", levelorder(root));
    testLevelOrder("Levelorder Iterative", levelorder_dfs(root));

    return 0;
}
